{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Amount of Time to Collect Garbage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: garbageCollection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #收集垃圾的最少总时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的字符串数组&nbsp;<code>garbage</code>&nbsp;，其中&nbsp;<code>garbage[i]</code>&nbsp;表示第 <code>i</code>&nbsp;个房子的垃圾集合。<code>garbage[i]</code>&nbsp;只包含字符&nbsp;<code>'M'</code>&nbsp;，<code>'P'</code> 和&nbsp;<code>'G'</code>&nbsp;，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 <strong>一</strong>&nbsp;单位的任何一种垃圾都需要花费&nbsp;<code>1</code>&nbsp;分钟。</p>\n",
    "\n",
    "<p>同时给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>travel</code>&nbsp;，其中&nbsp;<code>travel[i]</code>&nbsp;是垃圾车从房子 <code>i</code>&nbsp;行驶到房子 <code>i + 1</code>&nbsp;需要的分钟数。</p>\n",
    "\n",
    "<p>城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 <code>0</code>&nbsp;出发，<strong>按顺序</strong>&nbsp;到达每一栋房子。但它们 <strong>不是必须</strong>&nbsp;到达所有的房子。</p>\n",
    "\n",
    "<p>任何时刻只有 <strong>一辆</strong>&nbsp;垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 <strong>不能</strong>&nbsp;做任何事情。</p>\n",
    "\n",
    "<p>请你返回收拾完所有垃圾需要花费的 <strong>最少</strong>&nbsp;总分钟数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>garbage = [\"G\",\"P\",\"GP\",\"GG\"], travel = [2,4,3]\n",
    "<b>输出：</b>21\n",
    "<strong>解释：</strong>\n",
    "收拾纸的垃圾车：\n",
    "1. 从房子 0 行驶到房子 1\n",
    "2. 收拾房子 1 的纸垃圾\n",
    "3. 从房子 1 行驶到房子 2\n",
    "4. 收拾房子 2 的纸垃圾\n",
    "收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。\n",
    "收拾玻璃的垃圾车：\n",
    "1. 收拾房子 0 的玻璃垃圾\n",
    "2. 从房子 0 行驶到房子 1\n",
    "3. 从房子 1 行驶到房子 2\n",
    "4. 收拾房子 2 的玻璃垃圾\n",
    "5. 从房子 2 行驶到房子 3\n",
    "6. 收拾房子 3 的玻璃垃圾\n",
    "收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。\n",
    "由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。\n",
    "所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>garbage = [\"MMM\",\"PGM\",\"GP\"], travel = [3,10]\n",
    "<b>输出：</b>37\n",
    "<strong>解释：</strong>\n",
    "收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。\n",
    "收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。\n",
    "收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。\n",
    "总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= garbage.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>garbage[i]</code> 只包含字母&nbsp;<code>'M'</code>&nbsp;，<code>'P'</code>&nbsp;和&nbsp;<code>'G'</code>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= garbage[i].length &lt;= 10</code></li>\n",
    "\t<li><code>travel.length == garbage.length - 1</code></li>\n",
    "\t<li><code>1 &lt;= travel[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-amount-of-time-to-collect-garbage](https://leetcode.cn/problems/minimum-amount-of-time-to-collect-garbage/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-amount-of-time-to-collect-garbage](https://leetcode.cn/problems/minimum-amount-of-time-to-collect-garbage/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"G\",\"P\",\"GP\",\"GG\"]\\n[2,4,3]', '[\"MMM\",\"PGM\",\"GP\"]\\n[3,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        n = len(garbage)\n",
    "\n",
    "        m,p,g = False,False,False\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not g and \"G\" in garbage[i]:\n",
    "                g=True\n",
    "                ans+=sum(travel[:i])\n",
    "            if not m and \"M\" in garbage[i]:\n",
    "                m=True\n",
    "                ans+=sum(travel[:i])\n",
    "            if not p and \"P\" in garbage[i]:\n",
    "                p=True\n",
    "                ans+=sum(travel[:i])\n",
    "            if all([m,p,g]):\n",
    "                break\n",
    "\n",
    "        return len(\"\".join(garbage))+ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        d = dict(M=False, P=False, G=False)\n",
    "        a = [0] * 3\n",
    "        while travel:\n",
    "            c = Counter(garbage.pop())\n",
    "            t = travel.pop()\n",
    "            for i, n in enumerate('MPG'):\n",
    "                if n in c:\n",
    "                    d[n] = True\n",
    "                    a[i] += c[n]\n",
    "                if d[n]:\n",
    "                    a[i] += t\n",
    "        return sum(a) + len(garbage.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        s0, s = set(), 0\n",
    "        while travel:\n",
    "            g = garbage.pop()\n",
    "            t = travel.pop()\n",
    "            for i in 'MPG':\n",
    "                if i in g:\n",
    "                    s0.add(i)\n",
    "                if i in s0:\n",
    "                    s += t\n",
    "            s += len(g)\n",
    "        return s + len(garbage.pop())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        per_sum = [travel[0]]\n",
    "        for i in range(1,len(travel)):\n",
    "            per_sum.append(per_sum[-1]+travel[i])\n",
    "        \n",
    "        time_all = 0\n",
    "        for one in 'GPM':\n",
    "            per_have = -1\n",
    "            have = 0\n",
    "            for i in range(len(garbage)):\n",
    "                now_s = garbage[i].replace(one,'')\n",
    "                if len(garbage[i])-len(now_s)>0:\n",
    "                    have += len(garbage[i])-len(now_s)\n",
    "                    garbage[i] = now_s\n",
    "                    per_have = i\n",
    "            if have != 0:\n",
    "                if per_have != 0:\n",
    "                    time_all += (have)+per_sum[per_have-1]\n",
    "                else:\n",
    "                    time_all += (have)\n",
    "                \n",
    "        return time_all\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        ans = 0\n",
    "        garbage_n = len(garbage)\n",
    "        if garbage_n >= 1:\n",
    "            for i in range(1, garbage_n - 1): \n",
    "                travel[i] += travel[i - 1]\n",
    "        travel.insert(0, 0)\n",
    "        # 金属\n",
    "        t = 0\n",
    "        for i in range(garbage_n):\n",
    "            tmp = list(garbage[i])\n",
    "            if 'M' in tmp: t = i\n",
    "            while 'M' in tmp:\n",
    "                tmp.remove('M')\n",
    "                ans += 1\n",
    "            garbage[i] = \"\".join(tmp)\n",
    "        ans += travel[t]\n",
    "        \n",
    "        # 纸\n",
    "        t = 0\n",
    "        for i in range(garbage_n):\n",
    "            tmp = list(garbage[i])\n",
    "            if 'P' in tmp: t = i\n",
    "            while 'P' in tmp:\n",
    "                tmp.remove('P')\n",
    "                ans += 1\n",
    "            garbage[i] = \"\".join(tmp)\n",
    "        ans += travel[t]\n",
    "\n",
    "        \n",
    "        # 玻璃\n",
    "        t = 0\n",
    "        for i in range(garbage_n):\n",
    "            tmp = list(garbage[i])\n",
    "            if 'G' in tmp: t = i\n",
    "            while 'G' in tmp:\n",
    "                tmp.remove('G')\n",
    "                ans += 1\n",
    "            garbage[i] = \"\".join(tmp)\n",
    "        ans += travel[t]      \n",
    "\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        minutes = 0\n",
    "        car_g,car_p,car_m = 0,0,0\n",
    "        for i in range(len(garbage)):\n",
    "            minutes += len(garbage[i])\n",
    "            if 'G' in garbage[i]:\n",
    "                car_g = i\n",
    "            if 'M' in garbage[i]:\n",
    "                car_m = i\n",
    "            if 'P' in garbage[i]:\n",
    "                car_p = i\n",
    "        print(minutes,car_g,car_p,car_m)\n",
    "        minutes += sum(travel[0:car_g])\n",
    "        minutes += sum(travel[0:car_p])\n",
    "        minutes += sum(travel[0:car_m])\n",
    "        return minutes\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        \n",
    "        count_list = [0, 0, 0]\n",
    "        final_list = [0, 0, 0]\n",
    "        for idx, rb in enumerate(garbage):\n",
    "            if rb.count(\"M\") > 0:\n",
    "                count_list[0] += rb.count(\"M\")\n",
    "                final_list[0] = idx\n",
    "            if rb.count(\"P\") > 0:\n",
    "                count_list[1] += rb.count(\"P\")\n",
    "                final_list[1] = idx\n",
    "            if rb.count(\"G\") > 0:\n",
    "                count_list[2] += rb.count(\"G\")\n",
    "                final_list[2] = idx\n",
    "        travel = [0] + travel\n",
    "        print(sum(count_list))\n",
    "        print(sum(travel[:final_list[0] + 1]))\n",
    "        print(sum(travel[:final_list[1] + 1]))\n",
    "        print(sum(travel[:final_list[2] + 1]))\n",
    "        return sum(count_list) + sum(travel[:final_list[0] + 1]) + sum(travel[:final_list[1] + 1]) + sum(travel[:final_list[2] + 1]) \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        n = len(garbage)\n",
    "        all_time = len(garbage[0])\n",
    "        res = [0] * n\n",
    "        dic = {garbage[0]: 0}\n",
    "\n",
    "        for i in range(1, n):\n",
    "            res[i] = res[i-1] + travel[i-1]\n",
    "            for j in range(len(garbage[i])):\n",
    "                all_time += 1\n",
    "                if garbage[i][j] in dic:\n",
    "                    all_time -= res[dic[garbage[i][j]]]\n",
    "                all_time += res[i]\n",
    "                dic[garbage[i][j]] = i\n",
    "        return all_time\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        last_pos = {\"M\":0,\"P\":0,\"G\":0}\n",
    "        sumofgarbage = 0\n",
    "        res = 0 \n",
    "        for i in range(len(garbage)):\n",
    "            sumofgarbage += len(garbage[i])\n",
    "            if \"M\" in garbage[i]:\n",
    "                last_pos[\"M\"] = i\n",
    "            if \"P\" in garbage[i]:\n",
    "                last_pos[\"P\"] = i\n",
    "            if \"G\" in garbage[i]:\n",
    "                last_pos[\"G\"] = i\n",
    "        for k,v in last_pos.items():\n",
    "            res += sum(travel[:v])\n",
    "        res += sumofgarbage\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        res=len(list(\"\".join(garbage)))\n",
    "        for i in [\"M\",\"P\",\"G\"]:\n",
    "            for j in range(len(garbage)-1,-1,-1):#3,2,1,0\n",
    "                if i in garbage[j]:\n",
    "                    res+=sum(travel[:j])\n",
    "                    break\n",
    "        return res\n",
    "            \n",
    "        \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, arrs, travel, idx):\n",
    "        pre, res = 0, 0\n",
    "        for i, arr in enumerate(arrs):\n",
    "            if i > 0:\n",
    "                pre += travel[i - 1]\n",
    "            if arr[idx] > 0:\n",
    "                res += pre + arr[idx]\n",
    "                pre = 0\n",
    "        return res\n",
    "\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        arrs = []\n",
    "        for g in garbage:\n",
    "            cnt0, cnt1, cnt2 = 0, 0, 0\n",
    "            for ch in g:\n",
    "                if ch == 'M':\n",
    "                    cnt0 += 1\n",
    "                elif ch == 'P':\n",
    "                    cnt1 += 1\n",
    "                else:\n",
    "                    cnt2 += 1\n",
    "            arrs.append([cnt0, cnt1, cnt2])\n",
    "        res = 0\n",
    "        for i in range(3):\n",
    "            res += self.solve(arrs, travel, i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self,garbage, travel) -> int:\n",
    "        p=[]\n",
    "        q=[0,0,0]\n",
    "        ans=0\n",
    "        t1,t2,t3=0,0,0\n",
    "        for j,i in enumerate(garbage):\n",
    "            a=i.count('G')\n",
    "            b=i.count('M')\n",
    "            c=i.count('P')\n",
    "            m=[a,b,c]\n",
    "            if m[0]!= 0 :\n",
    "                q[0]=j\n",
    "            if m[1]!= 0 :\n",
    "\n",
    "                q[1]=j\n",
    "            if m[2]!= 0 :\n",
    "                q[2]=j\n",
    "            p.append(m)\n",
    "        for i in range(q[0]+1):\n",
    "            t1+=p[i][0]\n",
    "            if i>0:\n",
    "                t1+=travel[i-1]\n",
    "        for i in range(q[1]+1):\n",
    "            t2+=p[i][1]\n",
    "            if i>0:\n",
    "                t2+=travel[i-1]\n",
    "        for i in range(q[2]+1):\n",
    "            t3+=p[i][2]\n",
    "            if i>0:\n",
    "                t3+=travel[i-1]\n",
    "        print(t1,t2,t3)\n",
    "        return t1+t2+t3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        dirc = defaultdict(list)\n",
    "        for i,k in enumerate(garbage):\n",
    "            if \"M\" in k:\n",
    "                dirc[\"M\"].append(i)\n",
    "            if \"G\" in k:\n",
    "                dirc[\"G\"].append(i)\n",
    "            if \"P\" in k:\n",
    "                dirc[\"P\"].append(i)\n",
    "        presum = [0] + [0]*len(travel)\n",
    "        \n",
    "        for i in range(1,len(travel)+1):\n",
    "            presum[i] = travel[i-1] + presum[i-1]\n",
    "        ans = 0\n",
    "        # print(presum)\n",
    "        for trash in dirc.keys():\n",
    "            road = dirc[trash]\n",
    "            # print(road)\n",
    "            if len(road) == 1:\n",
    "                ans += Counter(garbage[road[0]])[trash] + presum[road[0]]\n",
    "            else:\n",
    "                ans += Counter(garbage[road[0]])[trash]\n",
    "                ans += presum[road[0]]\n",
    "                for i in range(1,len(road)):\n",
    "                    cnt = Counter(garbage[road[i]])[trash]\n",
    "                    time = presum[road[i]]-presum[road[i-1]]\n",
    "                    # print(time)\n",
    "                    ans += cnt + time\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        # 分别计算收垃圾的时间和行驶的时间\n",
    "        garbageTime = 0\n",
    "        n = len(garbage)\n",
    "        # 找到字母最后一次出现的位置 就是对应种类的垃圾车最远要去的房子\n",
    "        M_lastIndex, G_lastIndex, P_lastIndex = -1, -1, -1\n",
    "        for i,s in enumerate(garbage[::-1]):\n",
    "            garbageTime += len(s)\n",
    "            if 'M' in s:\n",
    "                M_lastIndex = max(M_lastIndex,n-i-1)\n",
    "            if 'G' in s:\n",
    "                G_lastIndex = max(G_lastIndex,n-i-1)\n",
    "            if 'P' in s:\n",
    "                P_lastIndex = max(P_lastIndex,n-i-1)\n",
    "\n",
    "        M_travelTime = 0 if M_lastIndex == -1 else sum(travel[:M_lastIndex])\n",
    "        G_travelTime = 0 if G_lastIndex == -1 else sum(travel[:G_lastIndex])\n",
    "        P_travelTime = 0 if P_lastIndex == -1 else sum(travel[:P_lastIndex])\n",
    "\n",
    "        res = garbageTime + M_travelTime + G_travelTime + P_travelTime\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        res=0\n",
    "        cur=\"M\"\n",
    "        travel.insert(0,0)\n",
    "        for p in range(0,3):\n",
    "            if p==1:\n",
    "                cur=\"P\"\n",
    "            elif p==2:\n",
    "                cur=\"G\"\n",
    "            time=[]\n",
    "            flag=0\n",
    "            for i in range(0,len(garbage)):\n",
    "                time.append(travel[i]+garbage[i].count(cur))\n",
    "            for i in range(len(time)-1,-1,-1):\n",
    "                if time[i]==travel[i] and flag==0:\n",
    "                    continue\n",
    "                else:\n",
    "                    flag=1\n",
    "                    res+=time[i]\n",
    "            print(time)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        dic = {}\n",
    "        cnt = {\"G\":0, \"P\":0, \"M\":0}\n",
    "\n",
    "        for i, s in enumerate(garbage):\n",
    "            for ch in s:\n",
    "                dic[ch] = i \n",
    "                cnt[ch] += 1\n",
    "        \n",
    "        pre = [0]\n",
    "        for i, a in enumerate(travel):\n",
    "            pre.append(pre[-1]+a)\n",
    "        \n",
    "        ans = 0\n",
    "        for g in dic:\n",
    "            ans += cnt[g]\n",
    "            ans += pre[dic[g]]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        ans = sum(len(s) for s in garbage)\n",
    "        for c in \"MPG\":\n",
    "            for i in range(len(garbage) - 1, -1, -1):\n",
    "                if c in garbage[i]:\n",
    "                    ans += sum(travel[:i])\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        n=len(garbage)-1\n",
    "        index=[0,0,0]\n",
    "        flag=[False,False,False]\n",
    "        res=[[0,0,0]for i in range(len(garbage))]\n",
    "        for k in range(len(garbage)-1,-1,-1):\n",
    "            for i in garbage[k]:\n",
    "                if i=='M':\n",
    "                    res[k][0]+=1\n",
    "                if i=='P':\n",
    "                    res[k][1]+=1\n",
    "                if i==\"G\":\n",
    "                    res[k][2]+=1\n",
    "            if flag[0]==False:\n",
    "                if res[k][0]!=0:\n",
    "                    flag[0]=True\n",
    "                    index[0]=k\n",
    "            if flag[1]==False:\n",
    "                if res[k][1]!=0:\n",
    "                    flag[1]=True\n",
    "                    index[1]=k\n",
    "            if flag[2]==False:\n",
    "                if res[k][2]!=0:\n",
    "                    flag[2]=True\n",
    "                    index[2]=k\n",
    "        time=sum(sum(i)for i in res)+sum(travel[:index[0]])+sum(travel[:index[1]])+sum(travel[:index[2]])\n",
    "        return time\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        n = len(garbage)\n",
    "        p = [[0]* 3 for _ in range(n)]\n",
    "        for i,g in enumerate(garbage):\n",
    "            p[i][0] = g.count('M')\n",
    "            p[i][1] = g.count('P')\n",
    "            p[i][2] = g.count('G')\n",
    "        pre = p[0][:]\n",
    "        i3 = [0]*3\n",
    "        travel_pre = list(accumulate([0]+travel))\n",
    "        for i in range(1,n):\n",
    "            for j in range(3):\n",
    "                pre[j] = pre[j] + p[i][j]\n",
    "                if p[i][j]:\n",
    "                    i3[j] = i\n",
    "        return pre[0] + travel_pre[i3[0]] +pre[1] + travel_pre[i3[1]] +pre[2] + travel_pre[i3[2]] \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        gars = ['G', 'P', 'M']\n",
    "        ret = 0\n",
    "        travel[0:0] = [0]\n",
    "        for i in range(1, len(travel)):\n",
    "            travel[i] += travel[i-1]\n",
    "        for g in gars:\n",
    "            last_idx = 0\n",
    "            for i in range(len(garbage)):\n",
    "                if g in garbage[i]:\n",
    "                    last_idx = i\n",
    "            ret += travel[last_idx]\n",
    "        ret += sum([len(_) for _ in garbage])\n",
    "        return ret\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:\n",
    "        ans=0\n",
    "        a,b,c=0,0,0\n",
    "        for i in range(1,len(travel)):\n",
    "            travel[i]+=travel[i-1]\n",
    "        for i in range(len(garbage)):\n",
    "            ans+=len(garbage[i])\n",
    "            for j in range(0,len(garbage[i])):\n",
    "                if i>0:\n",
    "                    if garbage[i][j]=='M':\n",
    "                        a=travel[i-1]\n",
    "                    elif garbage[i][j]=='G':\n",
    "                        b=travel[i-1]\n",
    "                    elif garbage[i][j]=='P':\n",
    "                        c=travel[i-1]      \n",
    "        ans+=a+b+c\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
